0498. 对角线遍历【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 模拟

1. 📝 题目描述

• leetcode

给你一个大小为 m x n 的矩阵 mat，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

---

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,4,7,5,3,6,8,9]

示例 2：

输入：mat = [[1,2],[3,4]]
输出：[1,2,3,4]

---

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 10^4
• 1 <= m * n <= 10^4
• -10^5 <= mat[i][j] <= 10^5

2. 🎯 s.1 - 模拟

c

int* findDiagonalOrder(int** mat, int matSize, int* matColSize, int* returnSize) {
    int m = matSize, n = matColSize[0];
    *returnSize = m * n;
    int* res = (int*)malloc(sizeof(int) * m * n);
    int r = 0, c = 0, up = 1;
    for (int i = 0; i < m * n; i++) {
        res[i] = mat[r][c];
        if (up) {
            if (c == n - 1) { r++; up = 0; }
            else if (r == 0) { c++; up = 0; }
            else { r--; c++; }
        } else {
            if (r == m - 1) { c++; up = 1; }
            else if (c == 0) { r++; up = 1; }
            else { r++; c--; }
        }
    }
    return res;
}

js

/**
 * @param {number[][]} mat
 * @return {number[]}
 */
var findDiagonalOrder = function (mat) {
  const m = mat.length,
    n = mat[0].length
  const res = []
  let r = 0,
    c = 0,
    up = true
  for (let i = 0; i < m * n; i++) {
    res.push(mat[r][c])
    if (up) {
      if (c === n - 1) {
        r++
        up = false
      } else if (r === 0) {
        c++
        up = false
      } else {
        r--
        c++
      }
    } else {
      if (r === m - 1) {
        c++
        up = true
      } else if (c === 0) {
        r++
        up = true
      } else {
        r++
        c--
      }
    }
  }
  return res
}

py

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        m, n = len(mat), len(mat[0])
        res = []
        r = c = 0
        up = True
        for _ in range(m * n):
            res.append(mat[r][c])
            if up:
                if c == n - 1:
                    r += 1; up = False
                elif r == 0:
                    c += 1; up = False
                else:
                    r -= 1; c += 1
            else:
                if r == m - 1:
                    c += 1; up = True
                elif c == 0:
                    r += 1; up = True
                else:
                    r += 1; c -= 1
        return res

• 时间复杂度：$O(m\times n)$
• 空间复杂度：$O(1)$（不计结果数组）

算法思路：

• 维护方向标志，交替向右上和左下遍历
• 到达边界时转向，根据当前位置决定右移还是下移